googologywikiaorg-20200223-history
Finite promise games
Friedman's finite promise games is a family of two-player games defined by Harvey Friedmanhttp://cs.nyu.edu/pipermail/fom/2009-September/014007.html. As the name implies, each of games is finite, and its length is actually predetermined. At each turn, one of the players (which we will call Alice) chooses an integer or a number of integers (an offering) and the other player (which we will call Bob) has to make promise restricting his future possible moves. Bob wins if and only if he can keep all the promises until the end of the game. Finite piecewise linear copy/invert games Call a function \(T: \mathbb{N}^k \mapsto \mathbb{N}\) piecewise linear iff it can be expressed using finitely many affine functions, using inequalities with integer coefficients to separate the function's pieces. Given a piecewise linear function \(T\), we say that a vector \(\mathbf{y}\) is a \(T\)-inversion of \(x\) iff \(T(\mathbf{y}) = x\). Given a piecewise linear function \(T: \mathbb{N}^k \mapsto \mathbb{N}\) and two positive integers \(n\) and \(s\), we define the finite piecewise linear copy/invert game \(G(T, n, s)\) as follows. \(G(T, n, s)\) is a two-player game alternating between Alice and Bob, with \(n\) rounds in total. Alice goes first. On her turn, Alice selects a number \(x \in s\), either of the form \(w!\) or \(y + z\), where \(y\) and \(z\) were previously played by Bob. \(x\) is called her offer. Bob either has the choice of accepting or rejecting the offer: * By accepting, he plays \(x\), and promises that none of the integers he ever plays will contain a \(T\) inversion of \(x\). * By rejecting, he plays a \(T\) inversion of \(x\) of his choice, and promises that none of the integers that he ever plays are \(x\). If Bob ever breaks one of his promises, he loses the game. If Bob lasts the entire \(n\) rounds without ever breaking a promise, he wins. dfa First of all, for a polynomial \(P\) in \(k\) variables we define special ''\(P\) ''inversion ''of a number \(x\) as a set of \(k\) numbers \(y_1,y_2,...,y_n<\frac{x}{2}\) such that \(P(y_1,y_2,...,y_k)=x\). Note that special inversions don't have to be unique. Now we define a game \(G(P,Q,n,s)\), where \(P,Q\) are polynomials in \(k\) variables and integer coefficients and \(n,s\) are nonzero natural numbers: the game will consist of \(n\) stages. At the beginning of every stage Alice chooses a number \(x\in-s,s\) which is either of the form \(P(y_1,y_2,...,y_k)\) or \(Q(y_1,y_2,...,y_k)\), where \(y_1,y_2,...,y_n\) have already been played by Bob before, or of the form \((z!)!\) for natural number \(z\). She offers this number to Bob, and now he has to make a choice. He can either: *accept \(x\), which means that he can play \(x\) (thus allowing Alice to later use it) and ''promise ''that among numbers played by Bob, at any point of the game, there will be no special \(P\) or \(Q\) inverse of \(x\), or *reject \(x\), which means that he will play some special \(P\) or \(Q\) inverse of \(x\) and ''promise that \(x\) will never be played by him. As mentioned, if Bob can finish the game while keeping all of the promises, then he wins, and Alice wins otherwise. Turns out that Bob always has a winning strategy in this game, no matter of the choice of \(P,Q,n,s\). This, however, doesn't have to be the case if we restrict Bob to accept all the double factorials Alice is offering him. Nevertheless, there exists a number \(N\), dependent on \(P,Q,n\) such that for all \(m,s>N\) Bob can win the game \(G(P,Q,n,s)\) if he is required to play all double factorials, provided they are larger than \(m\). We can turn above into an integer function as follows: we define \(F(x)\) as the least number \(N\) as above which will work for every choice of \(n\leq x\) and \(P,Q\) of degree, number of variables and coefficients of absolute value at most \(x\). As shown by Friedman, function \(F\) is extremely fast growing, exceeding every function provably recursive in theory SMAH, that is, ZFC augmented with, for every \(k\), a sentence "there exists a strongly \(k\)-Mahlo cardinal". It's worth noting that if we replace this infinite set of sentences with a single "for every \(k\) there exists a strongly \(k\)-Mahlo cardinal" we actually get quite stronger theory, denoted SMAH+, in which \(F\) is provable recursive. Sources See also Category:Functions Category:Combinatorics Category:Games